#include <vector>
#include <iostream>
#include <map>
#include <numeric>
#include <algorithm>
#include <iterator>

using namespace std;

multimap<int, char> changeMap(map<char, int>& mp){
    multimap<int, char> ret;
    // tansform(容器的首迭代器, 容器的末迭代器, 存放结果的容器, 要进行操作的一元函数对象或sturct、class)
    transform(mp.begin(), mp.end(), inserter(ret, ret.begin()), [](pair<char, int> a) { return pair<int, char>(a.second, a.first); });
    return ret;
}

string frequencySort(string s) {
    map<char, int> mp;
    for(char ch : s){
        auto r = mp.insert({ch, 1});
        if(!r.second){
            ++r.first->second;
        }
    }
    multimap<int, char> tmp = changeMap(mp);
    string ret; auto it = tmp.end();
    while(it-- != tmp.begin()){
        for(int i = 0; i < it->first; i++){
            ret += char(it->second);
        }
    }
    return ret;
}

int main(){
    string s = "tree";
    cout << frequencySort(s) << endl;
    return 0;
}